package 中等.分类讨论;

/**
 * 给定循环单调非递减列表中的一个点，写一个函数向这个列表中插入一个新元素 insertVal ，使这个列表仍然是循环升序的。
 * 给定的可以是这个列表中任意一个顶点的指针，并不一定是这个列表中最小元素的指针。
 * 如果有多个满足条件的插入位置，可以选择任意一个位置插入新的值，插入后整个列表仍然保持有序。
 * 如果列表为空（给定的节点是 null），需要创建一个循环有序列表并返回这个节点。否则。请返回原先给定的节点。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode.cn/problems/4ueAj6
 */
public class 排序的循环链表_offer029 {

    public static void main(String[] args) {

    }

    /**
     * 当链表只有一个节点时，插入节点可以放任意位置
     * 当链表大于一个节点时
     * curNode.val <= insertVal && insertVal <= curNode.next.val ,插入节点放到当前节点和下个节点的中间
     * curNode.val > curNode.next.val 时，一定是链表最大和最小值的分界处
     * 这时当 insertVal >= curNode.val , 说明插入值是最大值
     * 当 insertVal <= curNode.next.val 时，说明插入值是最小值
     * 都应该插入到 curNode 的后面
     * 循环一遍之后，未能找到插入位置，说明链表中的值全部相等，可以放任意位置
     *
     * @param head
     * @param insertVal
     * @return
     */
    public Node insert(Node head, int insertVal) {
        if (head == null) {
            head = new Node(insertVal);
            head.next = head;
            return head;
        }
        Node curNode = head;
        while (true) {
            if (curNode.val <= insertVal && insertVal <= curNode.next.val
                    || curNode.val > curNode.next.val && insertVal >= curNode.val
                    || curNode.val > curNode.next.val && insertVal <= curNode.next.val) {
                Node temp = curNode.next;
                curNode.next = new Node(insertVal);
                curNode.next.next = temp;
                return head;
            }
            curNode = curNode.next;
            if (curNode == head) {  // 说明已经遍历完成了一遍
                Node temp = curNode.next;
                curNode.next = new Node(insertVal);
                curNode.next.next = temp;
                return head;
            }
        }
    }

    class Node {
        public int val;
        public Node next;

        public Node() {
        }

        public Node(int _val) {
            val = _val;
        }

        public Node(int _val, Node _next) {
            val = _val;
            next = _next;
        }
    }

}

